from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = defaultdict(lambda : 0)
for i in a:
cnt[i] += 1
s = list(cnt.keys())
s.sort()
l, r = 0, len(s) - 1
mi, ma = s[l], s[r]
while l ^ r and k:
if cnt[mi] <= cnt[ma]:
c = min((s[l + 1] - mi) * cnt[mi], k)
mi += c // cnt[mi]
k -= c
l += 1
cnt[s[l]] += cnt[s[l - 1]]
else:
c = min((ma - s[r - 1]) * cnt[ma], k)
ma -= c // cnt[ma]
k -= c
r -= 1
cnt[s[r]] += cnt[s[r + 1]]
ans = ma - mi
print(ans)#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+1, INF = 1e18;
ll n, k, arr[N], pref[N];
bool val(ll x) {
ll res = INF;
// i = min, j = max
for (int i = 1, j = 1; i <= n; i++) {
while (j+1 <= n && arr[j+1] - arr[i] <= x) {
j++;
}
res = min(res, arr[i] * i - pref[i] + pref[n] - pref[j] - (arr[i] + x) * (n - j));
}
// i = max, j = min
for (int i = 1, j = 1; i <= n; i++) {
while (arr[i] - arr[j] > x) {
j++;
}
res = min(res, pref[n] - pref[i] - arr[i] * (n - i) + (arr[i] - x) * (j - 1) - pref[j - 1]);
}
return res <= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> arr[i];
sort(arr+1, arr+n+1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i-1] + arr[i];
}
ll lo = 0, hi = INF;
while (lo <= hi) {
ll mid = (lo + hi)/2;
if (val(mid)) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << lo << " " << endl;
}190D - Non-Secret Cypher | 1721B - Deadly Laser |
1721C - Min-Max Array Transformation | 1721A - Image |
1180C - Valeriy and Deque | 557A - Ilya and Diplomas |
1037D - Valid BFS | 1144F - Graph Without Long Directed Paths |
1228A - Distinct Digits | 355B - Vasya and Public Transport |
1230A - Dawid and Bags of Candies | 1530A - Binary Decimal |
1472D - Even-Odd Game | 441C - Valera and Tubes |
1328E - Tree Queries | 265A - Colorful Stones (Simplified Edition) |
296A - Yaroslav and Permutations | 967B - Watering System |
152A - Marks | 1398A - Bad Triangle |
137A - Postcards and photos | 1674D - A-B-C Sort |
334A - Candy Bags | 855A - Tom Riddle's Diary |
1417A - Copy-paste | 1038A - Equality |
1061A - Coins | 1676E - Eating Queries |
1447A - Add Candies | 1721D - Maximum AND |